package Solutions;

import java.util.Arrays;
import java.util.Stack;

/**
 * @Classname FindKthLargest
 * @Description TODO
 * @Date 2021/3/7 10:05
 * @Created by ASUS
 */
public class FindKthLargest {

    public int findKthLargest(int[] nums, int k) {

        if (k > nums.length) return Integer.MIN_VALUE;

        int index = getIndex(nums, 0, nums.length - 1, k);
//        if(index == nums.length - k){
//            return nums[index];
//        } else if(index < nums.length - k){
//            return
//        }
//        System.out.println(Arrays.toString(nums));
        return nums[index];
    }

    private int getIndex(int[] nums, int left, int right, int k) {
        int wall = left;
        int target = nums[right];
        for (int i = left; i < right; i++) {
            if (nums[i] < target) {
                swap(nums, i, wall++);
            }
        }
        swap(nums, wall, right);
        System.out.println(Arrays.toString(nums));
        if (wall == nums.length - k) {
            return wall;
        } else if (wall < nums.length - k) {
            return getIndex(nums, wall, right, k);
        } else {
            return getIndex(nums, left, wall - 1, k);
        }
    }

    private void swap(int[] nums, int index1, int index2) {
        int tmp = nums[index1];
        nums[index1] = nums[index2];
        nums[index2] = tmp;
    }

    public static void main(String[] args) {
        System.out.println(new FindKthLargest().findKthLargest(new int[]{3, 2, 3, 1, 2, 4, 5, 5, 6}, 4));
    }
}
